package Exp_3;
import java.util.Scanner;

public class MGraph implements IGraph {

    public final static int INFINITY = Integer.MAX_VALUE;
	private GraphKind kind;//图的种类标志
    private int vexNum, arcNum;//吐的当前顶点数和边数
    private Object[] vexs;//顶点
    private int[][] arcs;//邻接矩阵
    private static boolean[] visited;//设置访问标志数组

    static Scanner sc = new Scanner(System.in);

    public MGraph() {
        this(null, 0, 0, null, null);
    }

    //图的构造方法
    public MGraph(GraphKind kind, int vexNum, int arcNum, Object[] vexs, int[][] arcs) {
        this.kind = kind;
        this.vexNum = vexNum;
        this.arcNum = arcNum;
        this.vexs = vexs;
        this.arcs = arcs;
    }


    public void createGraph() {
        System.out.println("请输入图的类型：（UDG：无向图 DG：有向图）");
        GraphKind kind = GraphKind.valueOf(sc.next());
        switch (kind) {
            //构造无向图
            case UDG:
                createUDG();
                return;
            //构造有向图
            case DG:
                createDG();
                return;
        }
    }

    public int getVexNum() {
        return vexNum;
    }

    public Object getVex(int v) throws Exception {
        if (v < 0 && v >= vexNum) {
            throw new Exception("第" + v + "个顶点不存在");
        }
        return vexs[v];
    }

    public int locateVex(Object vex) {
        for (int v = 0; v < vexNum; v++) {
            if (vexs[v].equals(vex))
                return v;
        }
        return -1;
    }

    //有向图的邻接矩阵创建方式
    private void createDG() {
        System.out.println("请分别输入图的顶点数、图的边数");
        vexNum = sc.nextInt();
        arcNum = sc.nextInt();
        vexs = new Object[vexNum];
        System.out.println("请分别输入图的各个顶点：");
        for (int v = 0; v < vexNum; v++)
            vexs[v] = sc.next();
        arcs = new int[vexNum][vexNum];
        for (int i = 0; i < vexNum; i++)
            for (int j = 0; j < vexNum; j++)
                arcs[i][j] = INFINITY;
        System.out.println("请输入各个边的两个顶点：");
        for (int m = 0; m < arcNum; m++) {
            //输入顶点顺序:前连后
            int v = locateVex(sc.next());
            int u = locateVex(sc.next());
            arcs[v][u] = 1;
        }

    }

    //无向图的邻接矩阵创建方式
    private void createUDG() {
        System.out.println("请分别输入图的顶点数、图的边数");
        vexNum = sc.nextInt();
        arcNum = sc.nextInt();
        //构造数组 存储顶点
        vexs = new Object[vexNum];
        System.out.println("请分别输入图的各个顶点：");
        for (int v = 0; v < vexNum; v++)
            //顶点赋值
            vexs[v] = sc.next();
        //二维数组 存储顶点间距离
        arcs = new int[vexNum][vexNum];
        for (int i = 0; i < vexNum; i++)//初始化邻接矩阵
            for (int j = 0; j < vexNum; j++)
                arcs[i][j] = INFINITY;
        System.out.println("请输入各个边的两个顶点：");
        //连接输入的顶点
        for (int m = 0; m < arcNum; m++) {
            int v = locateVex(sc.next());
            int u = locateVex(sc.next());
            arcs[v][u] = arcs[u][v] = 1;
        }
    }

    //查找第一个临界点算法
    public int firstAdjVex(int v) throws Exception {
        if (v < 0 && v >= vexNum)
            throw new Exception("第" + v + "个顶点不存在!");
        for (int j = 0; j < vexNum; j++)
            if (arcs[v][j] != 0 && arcs[v][j] < INFINITY)
                return j;
        return -1;
    }

    //查找下一个临界点算法
    public int nextAdjVex(int v, int w) throws Exception {
        if (v < 0 && v >= vexNum)
            throw new Exception("第" + v + "个顶点不存在!");
        for (int j = w + 1; j < vexNum; j++)
            if (arcs[v][j] != 0 && arcs[v][j] < INFINITY)
                return j;
        return -1;
    }
    public int sum(int v) throws Exception {
        int sum = 0;
        if (v < 0 && v >= vexNum)
            throw new Exception("第" + v + "个顶点不存在！");
        for (int j = 0; j < vexNum; j++)
            if (arcs[v][j] != 0 && arcs[v][j] < INFINITY)
                sum++;
        for (int j = 0; j < vexNum; j++)
            if (arcs[j][v] != 0 && arcs[j][v] < INFINITY)
                sum++;
        return sum;
    }

    //图的广度优先搜索
    public static void BFSTraverse(IGraph G) throws Exception {

        visited = new boolean[G.getVexNum()];
        for (int v = 0; v < G.getVexNum(); v++)
            //访问标志数组初始化
            visited[v] = false;
        for (int v = 0; v < G.getVexNum(); v++)
            if (!visited[v])//v尚未访问
                BFS(G, v);
    }

    private static void BFS(IGraph G, int v) throws Exception {
        visited[v] = true;
        System.out.print(G.getVex(v).toString() + " ");
        LinkQueue Q = new LinkQueue();//辅助队列Q
        Q.offer(v);
        while (!Q.isEmpty()) {
            int u = (Integer) Q.pool();//队头元素出队列并赋值给u
            for (int w = G.firstAdjVex(u); w >= 0; w = G.nextAdjVex(u, w))
                if (!visited[w]) {
                    visited[w] = true;
                    System.out.print(G.getVex(w).toString() + " ");
                    Q.offer(w);
                }
        }

    }

    //图的深度优先
    public static void DFSTraverse(IGraph G) throws Exception {

        visited = new boolean[G.getVexNum()];
        for (int v = 0; v < G.getVexNum(); v++)
            //访问标志数组初始化
            visited[v] = false;
        for (int v = 0; v < G.getVexNum(); v++)
            if (!visited[v])//v尚未访问
                DFS(G, v);
    }

    public static void DFS(IGraph G, int v) throws Exception {
        //从第v个顶点出发递归地深度优先遍历图G
        visited[v] = true;
        System.out.print(G.getVex(v).toString() + " ");//访问地v个顶点
        for (int w = G.firstAdjVex(v); w >= 0; w = G.nextAdjVex(v, w))
            if (!visited[w])
                DFS(G, w);
    }

}